АППРОКСИМАЦИОННЫЕ АЛГОРИТМЫ И ПСЕВДОМЕТРИЧЕСКИЙ ВАРИАНТ ЗАДАЧИ КОММИВОЯЖЕРА 

Борисова Елена Сергеевна, аспирант, Тольяттинский государственный университет, г. Тольятти, e-lena-borisova@mail.ru
Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и прикладной информатики, Тольяттинский государственный университет, г. Тольятти, B.Melnikov@tltsu.ru

 004.021:519.8:519.724.6

Рассматривается классический подход к аппроксимационным алгоритмам, даются примеры, иллюстрирующие основное определение данных алгоритмов. Рассматриваются полиномиально-временные аппроксимационные схемы и совершенные полиномиально-временные аппроксимационные схемы. В качестве примера приводится псевдометрический вариант задачи коммивояжера, для которого пока не разработаны эффективные алгоритмы, дающие оптимальное решение.

аппроксимационные алгоритмы, относительная ошибка, аппроксимационное отношение, аппроксимационные схемы, псевдометрическая задача коммивояжера

 Скачать статью в формате PDF

1. Hromkovic J. Algorithmics for Hard Problems. Introduktion to Combinatorial Optimization, Randomization, Approximation and Heuristics / J. Hromkovic. – Springer, 2004. – 534 p.
2. Мельников, Б. Ф. Мультиэвристический подход к задачам дискретной оптимизации / Б. Ф. Мельников // Кибернетика и системный анализ (НАН Украины). – 2006. – № 3. – С. 32–42.